【题解】 [十二省联考2019]春节十二响 堆+启发式合并 luoguP5290 | Qiuly's blog!

【题解】 [十二省联考2019]春节十二响 堆+启发式合并 luoguP5290

Posted on | In | Comments:

要是我不是 $\texttt{HN}$ 的该多好，今年十二省联考两道傻逼题，一道异或粽子，一道十二响……

[十二省联考2019]春节十二响，启发式合并裸题。对于树中的一个节点 $u$ ，从其子树中选择一段的方式显然只能是从 $u$ 的所有子树中各选出一个节点。于是我们每一个节点开一个堆，存的就是其子树中(包括自己)的所有段的内存。

然后从下往上启发式合并即可，复杂度大约是 $O(nlogn)$ 。

启发式合并的具体代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge(int x, int y) {
    if(q[x].size()<q[y].size()) swap(q[x],q[y]);
    while(!q[y].empty()) {
        hep.push_back(max(q[x].top(),q[y].top()));
        q[x].pop(),q[y].pop();
        /*贪心选取*/
    }
    while(hep.size()) q[x].push(hep.back()),hep.pop_back();
    /*更新节点*/
}

void solve(int x) {
    for(int i=0,sz=G[x].size();i<sz;++i)
        solve(G[x][i]),merge(x,G[x][i]);/*将当前子树与之前枚举过的子树合并*/
    q[x].push(s[x]);
}

最后的总代码长度不超过 $40$ 行。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=2e5+7;

int n,f,s[N];
vector<int> hep,G[N];
priority_queue<int> q[N];

void merge(int x, int y) {
    if(q[x].size()<q[y].size()) swap(q[x],q[y]);
    while(!q[y].empty()) {
        hep.push_back(max(q[x].top(),q[y].top()));
        q[x].pop(),q[y].pop();
    }
    while(hep.size()) q[x].push(hep.back()),hep.pop_back();
}

void solve(int x) {
    for(int i=0,sz=G[x].size();i<sz;++i)
        solve(G[x][i]),merge(x,G[x][i]);
    q[x].push(s[x]);
}

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&s[i]);
    for(int i=2;i<=n;++i) scanf("%d",&f),G[f].push_back(i);
    solve(1);
    long long ans=0;
    while(!q[1].empty()) ans+=q[1].top(),q[1].pop();
    printf("%lld\n",ans);
    return 0;
}

本文标题:【题解】 [十二省联考2019]春节十二响 堆+启发式合并 luoguP5290

文章作者:Qiuly

发布时间:2019年04月19日 - 00:00

最后更新:2019年04月19日 - 19:41

原始链接:http://qiulyblog.github.io/2019/04/19/[题解]luoguP5290/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。